package com.gooluke.hashmap;

/**
 * @author gooluke
 * description
 * datetime 2025-04-15 15:40
 */
public class MyHashMap<K, V> {

    Node<K, V>[] table;
    private final int defaultCapacity = 16;
    private final float loadFactor = 0.75f;
    private int size = 0;

    public MyHashMap() {
        this.table = new Node[defaultCapacity];
    }

    public MyHashMap(int initialCapacity) {
        int finalCapacity = calculateCapacity(initialCapacity);
        System.out.println("finalCapacity = " + finalCapacity);
        this.table = new Node[finalCapacity];
    }

    public V put(K key, V value) {
        int index = indexOf(key);
        Node<K, V> kvNode = table[index];
        if (kvNode == null) {
            table[index] = new Node<>(key, value);
            size++;
            resizeIfNecessary();
            return null;
        }
        while (true) {
            if (kvNode.key.equals(key)) {
                V oldValue = kvNode.value;
                kvNode.value = value;
                return oldValue;
            }
            if (kvNode.next == null) {
                kvNode.next = new Node<>(key, value);
                size++;
                resizeIfNecessary();
                return null;
            }
            kvNode = kvNode.next;
        }
    }

    public V get(K key) {
        int index = indexOf(key);
        Node<K, V> kvNode = table[index];
        while (kvNode != null) {
            if (kvNode.key.equals(key)) {
                return kvNode.value;
            }
            kvNode = kvNode.next;
        }
        return null;
    }

    public V remove(K key) {
        int index = indexOf(key);
        Node<K, V> head = table[index];
        if (head == null) {
            return null;
        }
        if (head.key.equals(key)) {
            table[index] = head.next;
            size--;
            return head.value;
        }
        Node<K, V> pre = head;
        Node<K, V> current = head.next;
        while (current != null) {
            if (current.key.equals(key)) {
                pre.next = current.next;
                size--;
                return current.value;
            }
            pre = pre.next;
            current = current.next;
        }
        return null;
    }

    public int size() {
        return this.size;
    }

    private int indexOf(Object key) {
        return key.hashCode() & (table.length - 1);
    }

    private void resizeIfNecessary() {
        if (this.size < this.table.length * this.loadFactor) {
            return;
        }
        long start = System.currentTimeMillis();
        Node<K, V>[] newTable = new Node[table.length * 2];
        for (Node<K, V> head : this.table) {
            if (head == null) {
                continue;
            }
            Node<K, V> current = head;
            while (current != null) {
                int newIndex = current.key.hashCode() & (newTable.length - 1);
                Node<K, V> kvNode = newTable[newIndex];
                if (kvNode == null) {
                    newTable[newIndex] = current;
                    Node<K, V> next = current.next;
                    current.next = null;
                    current = next;
                } else {
                    Node<K, V> next = current.next;
                    current.next = newTable[newIndex];
                    newTable[newIndex] = current;
                    current = next;
                }
            }
        }
        this.table = newTable;
        System.out.println("执行了扩容，当前容量为：" + newTable.length + ",耗时：" + (System.currentTimeMillis() - start));
    }

    /**
     * 计算容量
     *
     * @param n 传入的容量
     * @return 计算后的容量，2的n次方
     */
    private int calculateCapacity(int n) {
        if (n <= this.defaultCapacity) return this.defaultCapacity;
        n--; // n = 1,048,572 (二进制: 11111111111111111100)
        n |= n >>> 1;  // 右移1位并按位或
        n |= n >>> 2;  // 右移2位并按位或
        n |= n >>> 4;  // 右移4位并按位或
        n |= n >>> 8;  // 右移8位并按位或
        n |= n >>> 16; // 右移16位并按位或
        return n + 1;  // 最终结果
    }

    public class Node<K, V> {
        private K key;
        private V value;
        private Node<K, V> next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

}
